В фирму “Black Label” поступили два заказа на изготовление ценников для
супермаркетов. В каждом заказе указаны количество ценников и цены, которые на
них должны быть напечатаны. Выведите по одному разу все цены, которые будут
напечатаны на ценниках при выполнении этих двух заказов.
Вход. Первая строка содержит количество n (n ≤ 105) ценников
для первого супермаркета. Вторая строка содержит список из n цен,
которые необходимо напечатать для первого супермаркета. Третья строка содержит
количество m (m ≤ 105) ценников для второго
супермаркета. Четвертая строка содержит список из m цен, которые
необходимо напечатать для второго супермаркета. Все входные числа целые и не
превышают 109.
Выход. Выведите значения, которые будут напечатаны на
ценниках, при этом каждая цена должна появиться только один раз. Цены должны
быть выведены в порядке возрастания.
|
Пример
входа |
Пример
выхода |
5100 25 300 400 120004
10 25
25 500 |
10 25 100 300 400 500 12000 |
структуры
данных – set
Анализ алгоритма
В задаче необходимо найти объединение двух множеств. Ее можно
решить при помощи множества set или бинарного дерева. Для этого занесем значения всех
ценников в выбранную структуру данных. При этом структура не должна содержать
дублирующих элементов. Например, в бинарное дерево новое
число вставляется только если его там еще нет. После этого нужно вывести все
элементы в порядке возрастания.
Реализация алгоритма
Значения
изготавливаемых ценников будем заносить во множество s.
set<int> s;
Читаем входные
данные. Заносим n ценников для
первого супермаркета во множество s.
scanf("%d",&n);
for(i = 0; i < n; i++)
{
scanf("%d",&val);
s.insert(val);
}
Заносим m ценников для
второго супермаркета во множество s.
scanf("%d",&m);
for(i = 0; i < m; i++)
{
scanf("%d",&val);
s.insert(val);
}
Выводим содержимое множества s.
for (int x : s)
printf("%d ", x);
printf("\n");
Реализация алгоритма – бинарное дерево
Дерево должно содержать только разные элементы (множество ценников
супермаркетов). Вставлять новое число в дерево
будем только если его там нет.
#include <stdio.h>
class TreeNode
{
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Tree
{
public:
TreeNode *head;
Tree() :
head(NULL) {};
void Insert(int val)
{
Insert(head, val);
}
void Insert(TreeNode *&tree, int val)
{
if (tree == NULL)
{
tree = new TreeNode(val);
return;
}
if (val == tree->val) return;
if (val < tree->val)
Insert(tree->left, val);
else
Insert(tree->right, val);
}
void InOrder(void)
{
InOrder(head);
}
void InOrder(TreeNode *tree)
{
if (tree == NULL) return;
InOrder(tree->left);
printf("%d ", tree->val);
InOrder(tree->right);
}
};
int n, val;
int main(void)
{
Tree *resTree = new Tree();
scanf("%d", &n);
while (n--)
{
scanf("%d", &val);
resTree->Insert(val);
}
scanf("%d", &n);
while (n--)
{
scanf("%d", &val);
resTree->Insert(val);
}
resTree->InOrder();
printf("\n");
return 0;
}
Java реализация
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
TreeSet<Integer> s = new TreeSet<Integer>();
int n = con.nextInt();
while(n-- > 0)
{
int val = con.nextInt();
s.add(val);
}
n = con.nextInt();
while(n-- > 0)
{
int val = con.nextInt();
s.add(val);
}
// Iterator iter = s.iterator();
// for(int i = 0; i < s.size(); i++)
//
System.out.print(iter.next() + " ");
for(int i : s)
System.out.print(i + " ");
con.close();
}
}
Java реализация – бинарное дерево
import java.util.Scanner;
class TreeNode
{
int val;
TreeNode left;
TreeNode right;
TreeNode(int x)
{
val = x;
left = null;
right = null;
}
}
class Tree
{
TreeNode head;
Tree()
{
head = null;
}
void Insert(int val)
{
head = Insert(head, val);
}
// objects are passed by copy
TreeNode
Insert(TreeNode tree, int val)
{
if (tree == null)
{
return new TreeNode(val);
}
if (val == tree.val) return tree;
if (val < tree.val)
tree.left = Insert(tree.left, val);
else
tree.right = Insert(tree.right, val);
return tree;
}
void InOrder()
{
InOrder(head);
}
void InOrder(TreeNode tree)
{
if (tree == null) return;
InOrder(tree.left);
System.out.print(tree.val + " ");
InOrder(tree.right);
}
}
public class Main
{
public static void main(String[] args)
{
Scanner
con = new Scanner(System.in);
Tree resTree = new Tree();
int n = con.nextInt();
for(int i = 0; i < n; i++)
{
int x = con.nextInt();
resTree.Insert(x);
}
n = con.nextInt();
for(int i = 0; i < n; i++)
{
int x = con.nextInt();
resTree.Insert(x);
}
resTree.InOrder();
System.out.println("");
con.close();
}
}
Python реализация
Читаем списки
ценников первого и второго супермаркетов.
n = int(input())
lst1 = list(map(int,input().split()))
m = int(input())
lst2 = list(map(int,input().split()))
Преобразуем списки
lst1 и
lst2 в множества и выполним над ними операцию объединения (“or”). В результате список
res содержит уникальные ценники из обоих супермаркетов в произвольном
порядке.
res = list(set(lst1) | set(lst2))
Выводим ценники в
порядке возрастания.
print(*sorted(res))
Python реализация – set
Значения
изготавливаемых ценников будем заносить во множество s.
s = set()
Читаем n ценников для
первого супермаркета и заносим их во множество s.
n = int(input())
lst1
= list(map(int,input().split()))
for x in lst1:
s.add(x)
Читаем m ценников для второго
супермаркета и заносим их во множество s.
m = int(input())
lst2
= list(map(int,input().split()))
for x in lst2:
s.add(x)
Выводим содержимое множества s в возрастающем порядке. Множество в Python не гарантирует упорядоченность элементов, поэтому следует воспользоваться функцией sorted().
for x in sorted(s):
print(x, end=' ')
print()